A network switch which has a multiplicity of ports disposed, for example, for receiving packet data from a variety of sources and other ports connected to groups of remote stations by intermediate devices, conveniently termed gateways, requires for its efficient operation a database by means of which a network address of a network destination and contained within an incoming packet is related to a media access control address, for example identifying a respective gateway, and an identification, such as masking data, of the port to which the intermediate device or gateway is connected. One way to decode incoming network addresses to use a hash table, indexed according to hashed addresses and consisting of pointers to entries in an associated data table of which the entries comprise a network address, a media access control address and a relevant port mask.
The state of the art is exemplified by the United States patent to Rostoker et al, U.S. Pat. No. 5,708,659, issued 13 Jan. 1998. That patent describes in considerable detail the organisation and detailed operation of a network switch in which predetermined numbers of bits from a packet address is selected to use a hash key, which is used to compute a table address. It further discloses the comparison of the contents of the table at that address with packet address information so that if the compared information matches, the packets may be transmitted over the port associated with the particular destination address. Other features of network switches, such as the storage of packets in buffer memories and the use of pointers, are fully described in the aforementioned patent. The performance of source address and destination address look-ups is also described in the European patent application EP-0594196 published 27 Apr. 1994. That describes a hybrid system in which searching of a relative large database is performed using a combination of programmable hash algorithms, binary search algorithms and a content-addressable memory.
Both network addresses and media access control addresses are normally quite wide, typically comprising 32 bits and 48 bits respectively. In practice however when remote stations are grouped by connection to a common intermediate device or gateway, the entries in the database contain a large degree of redundancy and therefore occupy substantially unnecessary space in a storage medium. In particular, where different remote stations share the same gateway, the entries in a data table indexed according to the network addresses of the remote stations will contain for each of the network addresses in a given group, identical media access control addresses and port masks for each of the stations in the group. A further disadvantage in known systems is a need to verify the network address relevant to an entry in a hash table of pointers. This arises in practice because network addresses of incoming packets are commonly reduced (by hashing) in width, so as to become a size matched for accessing the hash table.